A wide variety of design verification tools are required to produce a working integrated circuit from a functional specification. These tools analyze different parameters of a circuit design to insure that the circuit will function properly after it is fabricated. One important set of verification tools includes timing analysis tools which are widely used to predict the performance of very large scale integrated (VLSI) designs. Such timing analysis tools may be either static or dynamic. Dynamic timing analysis tools provide the most detailed and accurate information obtainable concerning the performance of a circuit. This type of timing analysis is often generated through simulation of a circuit model by simulation programs which operate at the transistor level. Examples of such circuit simulation programs are SPICE by University of California at Berkeley and ASTAP by IBM Corporation. For more information on SPICE, refer to "SPICE2: A Computer Program to Simulate Semiconductor Circuits," by L. W. Nagel, Technical Report ERL-M520, UC-Berkeley, May 1975. These dynamic timing analysis programs typically operate by solving matrix equations relating to the circuit parameters such as voltages, currents, and resistances. Additionally, such circuit simulation approaches to performance analysis are pattern dependent, or stated another way, the possible paths and the delays associated therewith depend upon a state of a controlling mechanism or machine of the circuit being simulated. Thus, the result of a dynamic timing analysis depends on the particular test pattern, or vector, applied to the circuit.
While such circuit simulation programs and dynamic timing analysis tools provide high accuracy, long simulation times are required because a large number of patterns must be simulated because the best and worst case patterns are not known before the simulation occurs. In fact, a number of simulations which must be performed is proportional to 2.sup.n, where "n" is a number of inputs to the circuit being simulated. Thus, for circuits having a large number of inputs, dynamic timing analysis is not always practical.
Static timing analysis tools are also widely used to predict the performance of VLSI designs. Static timing analyzers are often used on very large designs for which exhaustive timing accurate simulation (also called dynamic timing analysis) is impossible or impracticable. In static timing analysis, it is assumed that each signal switches independently in each machine cycle. Furthermore, in static timing analysis, only the best and worst possible rising and falling times are computed for each signal in the circuit; such times are typically determined in a single pass through a topologically-sorted circuit. When referring to a topologically sorted circuit, it should be noted that a signal time associated with each subcircuit of the circuit being tested is determined in a sequential nature. Therefore, the signal time associated with a first subcircuit whose output will be propagated to a second subcircuit must be determined before the signal time associated with the second subcircuit is calculated. Typical static analysis methods are described in "Timing Analysis of Computer Hardware," by Robert B. Hitchcock, Sr., et al., IBM J. Res. Develop., Vol. 26, No. 1, pp. 100-105 (1982).
Transistor-level timing analyzers eliminate the need for predefined cell libraries by decomposing circuits into channel-connected components and automatically computing the delay of each component. Such channel connected components are non-intersecting groups of transistors which are connected by source and drain terminals to one another and to supply and ground nets, or connections. Each channel connect component can be analyzed independently to compute the worst case delays from each input to each output for both rising and falling signals.
To compute a delay in a channel-connected component, it is necessary to determine which transistors are conducting and non-conducting during a particular delay analysis. This is commonly done by tracing paths in the channel-connected component from output nets to supply and ground nets to find all possible pull-up and pull-down paths. Delays for each path are computed independently by enabling all transistors in the path and disabling all other transistors in the channel-connected component to ensure that all other paths are inactive.
This approach works well for most CMOS circuits but assumes that the input signals to a channel-connected component are logically independent. Dependencies among input signals can cause the approach to fail in at least four significant ways:
1. Input signal dependencies can force other paths to be enabled along with the path of interest, so that the delay of the path overestimates the actual delay. PA1 2. Input signal dependencies can force signals to switch simultaneously. PA1 3. Input signal dependencies can make a path through a channel-connected component unsensitizable, such that any delay associated with the path is logically impossible. PA1 4. Input signal dependencies can allow side transistors to be turned on, adding to the capacitive load seen during the switching event.
The first type of failure is illustrated in FIG. 1, which shows a domino AND gate 100 designed to have a balanced input-to-output delay on each input-to-output path. Approaches based on path tracing will compute the delay of each pull-down path separately and overestimate the delay of the gate because in reality, when any one pull-down path is enabled, all three are enabled and are working together to pull down node Y.
The second type of failure is illustrated in FIG. 2, which shows a complementary pass-transistor circuit 200 Signal C.sub.N is the inverse of signal C and will switch in response to a transition on C. A measurement of delay from C to Q should include the effects of a transition on C.sub.N.
The third type of failure is illustrated in FIG. 3, which illustrates a two-bit crossbar circuit. Depending on the values of select lines S.sub.0 and S.sub.1, nets X.sub.1 and X.sub.2 can be connected to nets X.sub.3 and X.sub.4 respectively, or nets X.sub.4 and X.sub.3 respectively. For the circuit to operate correctly, select lines S.sub.0 and S.sub.1 can never be high at the same time. Techniques that ignore the relationship between S.sub.0 and S.sub.1 will trace false paths in this circuit and produce overly pessimistic results. For example, starting at net X.sub.4, a path can be traced back through transistors M.sub.24 (302), M.sub.23 (304), and M.sub.13 (306) to net X.sub.1. Including this path in the delay calculation will produce an overly pessimistic delay from X.sub.1 to X.sub.4, since the path can never be enabled, or sensitized, and all sensitizable paths go through a single transistor in the crossbar. Previous approaches have attempted to eliminate these paths by associating directions with individual transistors. However, depending on the circuits attached to nets X.sub.1, X.sub.2, X.sub.3, and X.sub.4, the pass transistors may be truly bidirectional, and the only way to eliminate the paths automatically is to account for the logical dependencies among inputs S.sub.0 and S.sub.1.
The fourth type of failure is illustrated in FIG. 4 which shows a subcircuit of a dynamic carry lookahead adder circuit 400. The subcircuit is used to combine "generate (G)", "zero" (Z), and "propagate" (P) bits of intermediate stages into "group generate" (GG), "group zero" (GZ), and "group propagate" (GP) bits. The structure of the adder ensures that for each trio of "generate", "zero", and "propagate" bits, at most one signal is high. Delay calculation techniques that don't account for this fact can overestimate switching delays. For example, when computing the delay from input ZB to node IZ, transistors M.sub.ZB and M.sub.c must be enabled to cause the voltage at node IZ to fall when the voltage on input ZB rises. Values for the remaining inputs are not directly specified and are often set to disable all other transistors in the subcircuit. However, this can cause the delay to be underestimated because when ZA has a high voltage, a transistor M.sub.ZA is enabled and an additional capacitance must be discharged before IZ can completely fall. Many path-based timing analyzers allow a limited number of transistors adjacent to the path to be enabled to account for this extra capacitance.
Typically, a user will specify the number of transistors to enable on any side path to a path being analyzed. However, this limit is arbitrary and if set too high, can cause the true path to be short-circuited. For example, in FIG. 4, if the limit is set to 2, transistors M.sub.ZA and M.sub.PB would be enabled, short-circuiting the path through M.sub.ZB and making it impossible to measure the delay from input ZB. A more sophisticated delay calculation technique would set side inputs to values that satisfied dependencies among input signals while continuing to sensitize the path of interest. For the circuit in FIG. 4, setting input ZB high forces inputs GB and PB low and if input ZA is set high to maximize the capacitance seen at output IZ, then inputs GA and PA must also be low. This combination of input values accurately reflects the operating environment of the circuit and provides a worst-case sensitization of the path being analyzed.
As these examples illustrate, although the traditional transistor level static timing analysis approach is adequate for many logic circuits, it does not provide for proper timing analysis of logic circuits with parallel conduction paths or with logical constraints on input signals. Therefore, a need exists for a timing analysis approach which provides for proper timing analyses for logic circuits whose performance may be affected by such parallel paths and logical constraints.